package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
 *
 * @author Administrator
 * @date 2019/5/17 10:57
 */
public class SwapNumToMax {

    /**
     * 将所有字节进行排序生成有序数组tmp
     * 从数字最左端开始遍历，再从tmp由大到小遍历
     * 取出大于当前字符，并且下标大于当前数字下标A的字符所在数字的最大下标B
     * 替换下标A和B的字符
     *
     * @param num
     * @return
     */
    public static int maximumSwap(int num) {
        if (num <= 11) {
            return num;
        }
        String str = String.valueOf(num);
        char[] tmp = str.toCharArray();
        Arrays.sort(tmp);
        int maxIndex = -1;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            for (int j = tmp.length - 1; j >= 0; j--) {
                if (tmp[j] <= c) {
                    break;
                }
                int index = str.lastIndexOf(tmp[j]);
                if (index > i) {
                    maxIndex = index;
                    break;
                }
            }
            if (maxIndex != -1) {
                tmp = str.toCharArray();
                char d = tmp[maxIndex];
                tmp[maxIndex] = tmp[i];
                tmp[i] = d;
                return Integer.valueOf(String.valueOf(tmp));
            }
        }
        return num;
    }

    @Test
    public void maximumSwap() {
        Assert.assertEquals(99910, maximumSwap(99901));
        Assert.assertEquals(999101, maximumSwap(199901));
    }
}
